package www.study.com;

import java.util.Arrays;

//最接近的三数之和 https://leetcode.cn/problems/3sum-closest/
public class code15 {
    public static void main(String[] args) {

    }

    class Solution {
        public int threeSumClosest(int[] nums, int target) {
            Arrays.sort(nums);
            int res = Integer.MAX_VALUE;
            for(int i = 0 ; i < nums.length ; i++){
                if(i > 0 && nums[i] == nums[i - 1]) continue;
                int lef = i + 1;
                int rig = nums.length - 1;
                while(lef < rig){
                    if(Math.abs(nums[i] + nums[lef] + nums[rig] - target) < Math.abs(res - target)){
                        res = nums[i] + nums[lef] + nums[rig];
                        ////这里要注释掉，本来这里是为了去重操作，但是对于用例[-1000,-5,-5,-5,-5,-5,-1,-1,-1]，-15会忽略[-5,-5,-5]这个组合
                        // while(lef < rig && nums[lef] == nums[lef + 1]) lef++;
                        // while(lef < rig && nums[rig - 1] == nums[rig]) rig--;
                    }
                    if(res == target) return res;
                    if(nums[i] + nums[lef] + nums[rig] >= target) rig--;
                    else lef++;
                }
            }
            return res;
        }
    }
}
